const { ListNode, LinkedList } = require('../2. 链表/1. 链表基础/1. 建立线性链表.js')
// 给定一个单链表的头节点的head
// 要求将链表中的奇数位置上的节点排在前面，偶数位置上的节点排在后面，返回新的链表节点
// 要求空间复杂度为O(1)

// 思路，将链表中奇数位置上的节点和偶数位置上的节点拆分为两个链表，再将偶数节点连接到奇数节点的末尾

function oddEvenList(head) {
    // 少于三个节点直接返回
    if (!head || !head.next || !head.next.next) {
        return head
    }
    let odd = head
    let even = head.next
    let evenHead = head.next
    let cur = head.next.next
    let isOdd = true
    while (cur) {
        if (isOdd) {
            odd.next = cur
            odd = cur
        } else {
            even.next = cur
            even = cur
        }
        isOdd = !isOdd
        cur = cur.next
    }
    odd.next = evenHead
    even.next = null
    return head
}

let head = [1, 2, 3, 4, 5]
let node = new LinkedList(head)
console.log(oddEvenList(node.head))